//
//  main.cpp
//  单链表的模拟实现
//
//  Created by Yan Zihao on 2024/10/19.
//

#include <stdio.h>
#include <assert.h>
typedef int SLTDataType;

typedef struct SListNode
{
    int data;
    struct SListNode* next;  //指向下一个节点的指针
}SLTNode;

//打印元素
void SLTPrint(SLTNode* phead)
{
    SLTNode* pcur = phead;
    while (pcur)
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

//新建内存空间
SLTNode* SLTBuyNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    //空链表和非空链表判断
    SLTNode* newnode = SLTBuyNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //找尾节点
        SLTNode* ptail = *pphead;
        while (ptail->next)
        {
            ptail = ptail->next;
        }
        //ptail此时就是指向尾节点
        ptail->next = newnode;
    }
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}
//尾部删除
void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);
    //链表只有一个节点
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    //链表有多个节点
    else
    {
        SLTNode* prev = *pphead;//前节点
        SLTNode* ptail = *pphead;
        while (ptail->next)
        {
            prev = ptail;
            ptail = ptail->next;
        }
        //prev ptail
        free(ptail);
        ptail = NULL;
        prev->next = NULL;
    }
}
//头部删除
void SLTPopFront(SLTNode** pphead)
{
    //链表不能为空
    assert(pphead && *pphead);

    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* pcur = phead;
    while (pcur)
    {
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead && *pphead);
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    SLTNode* prev = *pphead;
    //若 pos == *pphead，说明是头插,直接调用头插代码
    if (pos == *pphead)
    {
        SLTPushFront(pphead, x);
    }
    else
    {
        while (prev->next != pos)
        {
            prev = prev->next;
        }

        newnode->next = pos;
        prev->next = newnode;
    }
    
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);
    assert(pos);

    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
        prev = prev->next;
    }

    prev->next = pos->next;
    free(pos);
    pos = NULL;
}

void SListTest02()
{
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushFront(&plist, 2);
    SLTPrint(plist);
}
int main(void)
{
    SListTest02();
    return 0;
}
